﻿/*
题目: 替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

https://leetcode.cn/problems/longest-repeating-character-replacement/description/*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int characterReplacement(string s, int k) {
        // 维护一个最大 cnt + k 的窗口
        int counter[26] = { 0 };
        int res = 0;
        int maxlen = 0;
        int left = 0;

        for (int i = 0; i < s.size(); i++) {
            if (maxlen < ++counter[s[i] - 'A']) {
                maxlen = counter[s[i] - 'A'];
            }

            if (left < i && i - left + 1 > maxlen + k) {
                counter[s[left++] - 'A'] --;
            }
            res = max(res, i - left + 1);
        }

        return res;
    }
};
